﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using social_network_tool;

namespace maximal_clique
{
    class graph_operation
    {
        /// <summary>
        /// Tạo đồ thị từ danh sách cạnh
        /// Bắt đầu đỉnh theo thứ tự từ 1
        /// Định dạng: Dinh1_Dinh2
        /// </summary>
        /// <param name="listCanh"></param>
        /// <param name="IsUndirectGraph"></param>
        /// <returns></returns>
        public static List<List<int>> ChuyenSangDanhSachKe(List<int> dinh1, List<int> dinh2, bool IsUndirectGraph)
        {
            List<List<int>> danhsackKe = new List<List<int>>();
            int iddinh1, iddinh2;
            for (int i = 0; i < dinh1.Count; i++)
                if (dinh1[i] >= 1 && dinh2[i] >= 1)
                {
                    while (danhsackKe.Count < dinh1[i])
                        danhsackKe.Add(new List<int>());
                    while (danhsackKe.Count < dinh2[i])
                        danhsackKe.Add(new List<int>());

                    iddinh1 = dinh1[i] - 1;
                    iddinh2 = dinh2[i] - 1;

                    if (!danhsackKe[iddinh1].Contains(iddinh2))
                        danhsackKe[iddinh1].Add(iddinh2);

                    if (IsUndirectGraph && !danhsackKe[iddinh2].Contains(iddinh1))
                        danhsackKe[iddinh2].Add(iddinh1);
                }
            return danhsackKe;
        }

        /// <summary>
        /// Chuyển từ danh sách kề sang ma trận.
        /// </summary>
        /// <param name="danhsachKe"></param>
        /// <param name="level"></param>
        /// <param name="IsUndirectGraph"></param>
        /// <returns></returns>
        public static float[,] ChuyenSangMatran(List<List<int>> danhsachKe, ref int level, bool IsUndirectGraph)
        {
            level = danhsachKe.Count;
            float[,] matrix = new float[level, level];
            for (int i = 0; i < danhsachKe.Count; i++)
            {
                matrix[i, i] = 1f;
                foreach (int dinhke in danhsachKe[i])
                {
                    matrix[i, dinhke] = 1f;
                    if (IsUndirectGraph)
                        matrix[dinhke, i] = 1f;
                }
            }
            return matrix;
        }


        public static void LietKeTatCaDuongDi(List<List<int>> danhsachke, int dinhbatdau, int dinhketthuc,
            List<int> duongdi, ref List<List<int>> dsDuongDi)
        {
            if (duongdi.Contains(dinhketthuc))
            {
                dsDuongDi.Add(new List<int>());
                foreach (int dinh in duongdi)
                    dsDuongDi[dsDuongDi.Count - 1].Add(dinh);
                return;
            }
            else
            {
                int count = 0;
                foreach (int dinhke in danhsachke[dinhbatdau])
                    if (duongdi.Contains(dinhke) == false)
                    {
                        duongdi.Add(dinhke);
                        LietKeTatCaDuongDi(danhsachke, dinhke, dinhketthuc, duongdi, ref dsDuongDi);
                        duongdi.RemoveAt(duongdi.Count - 1);
                        count++;
                    }
                if (count == 0)
                    return;
            }
        }

        public static List<List<int>> TimTatCaDuongDiNganNhat(List<List<int>> danhsachke, float[,] matrix, int level)
        {
            List<int> duongdi = new List<int>();
            List<List<int>> dsDuongDi = new List<List<int>>();
            List<List<int>> dsDuongDiNganNhat = new List<List<int>>();
            List<int> listdsDinhNganNhat = new List<int>();
            int count = danhsachke.Count;
            float minLength;
            float tam;
            for (int i = 0; i < danhsachke.Count; i++)
                for (int j = 0; j < danhsachke.Count; j++)
                    if (i != j)
                    {
                        duongdi = new List<int>();
                        duongdi.Add(i);
                        dsDuongDi = new List<List<int>>();
                        LietKeTatCaDuongDi(danhsachke, i, j, duongdi, ref dsDuongDi);

                        //dsDuongDi.Sort(CoreFunction.Compare_CountListInt_asc);
                        //if (dsDuongDi.Count > 0)
                        //{
                        //    minLength = dsDuongDi[0].Count;

                        //    for (int k = 0; k < dsDuongDi.Count; k++)
                        //        if (dsDuongDi[k].Count == minLength)
                        //        {
                        //            dsDuongDiNganNhat.Add(new List<int>());
                        //            foreach (int dinh in dsDuongDi[k])
                        //                dsDuongDiNganNhat[dsDuongDiNganNhat.Count - 1].Add(dinh);
                        //        }
                        //        else
                        //            break;
                        //}

                        if (dsDuongDi.Count > 0)
                        {
                            listdsDinhNganNhat = new List<int>();
                            minLength = CoreFunction.DoDaiDuongDi(matrix, level, dsDuongDi[0]);
                            listdsDinhNganNhat.Add(0);
                            for (int k = 1; k < dsDuongDi.Count; k++)
                            {
                                tam = CoreFunction.DoDaiDuongDi(matrix, level, dsDuongDi[k]);
                                if (tam == minLength)
                                    listdsDinhNganNhat.Add(k);
                                else
                                    if (tam < minLength)
                                    {
                                        listdsDinhNganNhat = new List<int>();
                                        listdsDinhNganNhat.Add(k);
                                        minLength = tam;
                                    }
                            }

                            foreach (int id in listdsDinhNganNhat)
                                dsDuongDiNganNhat.Add(dsDuongDi[id]);
                        }
                    }
            return dsDuongDiNganNhat;
        }

        public static int TinhSoDuongDiQuaDinh(List<List<int>> dsDuongDi, int dinh)
        {
            int count = 0;
            foreach (List<int> duongdi in dsDuongDi)
                if (duongdi[0] != dinh && duongdi[duongdi.Count - 1] != dinh && duongdi.Contains(dinh))
                    count++;
            return count;
        }

        //public static List<float> TinhBetweeneesCentrality(List<List<int>> danhsachKe)
        //{
        //    List<List<int>> dsDuongDiNganNhat = TimTatCaDuongDiNganNhat(danhsachKe);
        //    List<float> result = new List<float>();
        //    int countDsDuongDiNganNhat = dsDuongDiNganNhat.Count;
        //    for (int i = 0; i < danhsachKe.Count; i++)
        //        result.Add((float)Math.Round((float)TinhSoDuongDiQuaDinh(dsDuongDiNganNhat, i) / countDsDuongDiNganNhat, 2));

        //    result = CoreFunction.ChuanHoa(result);
        //    return result;
        //}

        public static float TinhBetWeenCentrality_DoThiVoHuong(int level, int dinh, List<List<int>> dsDuongDiNganNhat)
        {
            int count = 0;
            float sum = 0f;
            int total = 0;
            int temp = 0;
            for (int i = 0; i < level; i++)
                for (int j = 0; j < level; j++)
                {
                    count++;
                    total = 0;
                    temp = 0;
                    foreach (List<int> duongdi in dsDuongDiNganNhat)
                        if (duongdi[0] == i && duongdi[duongdi.Count - 1] == j && i != dinh && j != dinh)
                        {
                            total++;
                            if (duongdi.Contains(dinh) && duongdi.Count > 2)
                                temp++;
                        }
                    if (total != 0)
                    {
                        sum += (float)temp / total;
                    }
                }
            //sum = (float)Math.Round(sum / count, 2);
            return sum;
        }

        public static List<float> TinhBetweeneesCentrality_DoThiVoHuong(List<List<int>> danhsachKe, float[,] matrix)
        {
            int level = danhsachKe.Count;
            List<float> result = new List<float>();
            List<List<int>> dsDuongDiNganNhat = TimTatCaDuongDiNganNhat(danhsachKe, matrix, level);
            for (int i = 0; i < level; i++)
                result.Add(TinhBetWeenCentrality_DoThiVoHuong(level, i, dsDuongDiNganNhat));
            //result = CoreFunction.ChuanHoa(result);
            return result;
        }

        private static float TinhClosenessCentralityMotDinh(List<List<int>> dsDuongDi, int dinh, float[,] matrix, int level)
        {
            int count = 0;
            float length = 0f;
            List<int> listdinhdiqua = new List<int>();
            foreach (List<int> duongdi in dsDuongDi)
                if (duongdi[0] == dinh && listdinhdiqua.Contains(duongdi[duongdi.Count - 1]) == false)
                {
                    count++;
                    length += CoreFunction.DoDaiDuongDi(matrix, level, duongdi);
                    listdinhdiqua.Add(duongdi[duongdi.Count - 1]);
                }

            if (count > 0)
                //return (float)Math.Round((float)length / count, 2);
                return (float)Math.Round(1f / length, 2);
            else
                return 0;
        }

        public static List<float> TinhClosenessCentrality(List<List<int>> danhsachKe, float[,] matrix, int level)
        {
            List<List<int>> dsDuongDiNganNhat = TimTatCaDuongDiNganNhat(danhsachKe, matrix, level);
            List<float> result = new List<float>();

            for (int i = 0; i < danhsachKe.Count; i++)
                result.Add(TinhClosenessCentralityMotDinh(dsDuongDiNganNhat, i, matrix, level));

            return result;
        }

        public static List<float> TinhDegreeCentrality(List<List<int>> danhsachKe)
        {
            List<float> result = new List<float>();
            int level = danhsachKe.Count;
            for (int i = 0; i < level; i++)
                result.Add((float)Math.Round((float)danhsachKe[i].Count / (level - 1), 2));

            return result;
        }

        private static float TinhClusterCoeff_1Dinh(int Dinh, List<List<int>> danhsachKe)
        {
            int count = danhsachKe[Dinh].Count; /// trừ đỉnh đang xét ra          
            int canh = 0;
            for (int i = 0; i < danhsachKe[Dinh].Count; i++)
                for (int j = 0; j < danhsachKe[Dinh].Count; j++)
                    if (i != j && danhsachKe[danhsachKe[Dinh][i]].Contains(danhsachKe[Dinh][j]))
                        canh++;
            if (count > 1)
                return (float)Math.Round((float)canh / (count * (count - 1)), 3);
            else
                return 0;
        }

        public static List<float> TinhClusterCoeff(List<List<int>> dsKe)
        {
            int level = dsKe.Count;
            List<float> result = new List<float>();
            for (int i = 0; i < level; i++)
                result.Add(TinhClusterCoeff_1Dinh(i, dsKe));

            return result;
        }

        public static float[] Faster_TinhBetWeenCloseCentrality_DoThiKhongTrongSo(List<List<int>> danhsachKe, out float[] closeness)
        {
            Stack<int> stack;
            Queue<int> queue;
            List<List<int>> perdecessors;
            int[] anpha;
            int[] distance;
            float[] between = new float[danhsachKe.Count];
            closeness = new float[danhsachKe.Count];
            float[] beta;
            int w, sumdistance;

            for (int i = 0; i < danhsachKe.Count; i++)
            {
                stack = new Stack<int>();
                queue = new Queue<int>();

                perdecessors = new List<List<int>>();
                for (int j = 0; j < danhsachKe.Count; j++)
                    perdecessors.Add(new List<int>());

                anpha = new int[danhsachKe.Count];
                anpha[i] = 1; /// ngược lại bằng 0

                distance = new int[danhsachKe.Count];
                for (int j = 0; j < danhsachKe.Count; j++)
                    distance[j] = -1;
                distance[i] = 0;

                queue.Enqueue(i);
                while (queue.Count != 0)
                {
                    int v;
                    v = queue.Dequeue();
                    stack.Push(v);
                    foreach (int neighbor in danhsachKe[v])
                    {
                        /// neighbor found for the first time ?
                        if (distance[neighbor] < 0)
                        {
                            queue.Enqueue(neighbor);
                            distance[neighbor] = distance[v] + 1;
                        }
                        /// shortest path to w via v ?
                        if (distance[neighbor] == distance[v] + 1)
                        {
                            anpha[neighbor] += anpha[v];
                            perdecessors[neighbor].Add(v);
                        }
                    }
                }

                beta = new float[danhsachKe.Count];

                while (stack.Count != 0)
                {
                    w = stack.Pop();
                    foreach (int v in perdecessors[w])
                        beta[v] = beta[v] + ((float)anpha[v] / anpha[w]) * (1 + beta[w]);
                    if (w != i)
                        between[w] = between[w] + beta[w];
                }

                /// Calculate closeness
                sumdistance = 0;
                foreach (int d in distance)
                {
                    sumdistance += d;

                }
                if (sumdistance > 0f)
                    closeness[i] = (float)1 / sumdistance;
            }
            for (int i = 0; i < between.Length; i++)
            {
                between[i] = (float)Math.Round(between[i], 2);
                closeness[i] = (float)Math.Round(closeness[i], 2);
            }
            return between;
        }

    }
}
